home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / idict.h < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  10.0 KB  |  274 lines
  1. /* Copyright (C) 1989, 1995, 1997, 1998 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: idict.h,v 1.2 2000/09/19 19:00:43 lpd Exp $ */
  20. /* Interfaces for Ghostscript dictionary package */
  21.  
  22. #ifndef idict_INCLUDED
  23. #  define idict_INCLUDED
  24.  
  25. #include "iddstack.h"
  26.  
  27. /*
  28.  * Contrary to our usual practice, we expose the (first-level)
  29.  * representation of a dictionary in the interface file,
  30.  * because it is so important that access checking go fast.
  31.  * The access attributes for the dictionary are stored in
  32.  * the values ref.
  33.  */
  34. struct dict_s {
  35.     ref values;            /* t_array, values */
  36.     ref keys;            /* t_shortarray or t_array, keys */
  37.     ref count;            /* t_integer, count of occupied entries */
  38.     /* (length) */
  39.     ref maxlength;        /* t_integer, maxlength as seen by client. */
  40.     ref memory;            /* foreign t_struct, the allocator that */
  41.     /* created this dictionary */
  42. #define dict_memory(pdict) r_ptr(&(pdict)->memory, gs_ref_memory_t)
  43. };
  44.  
  45. /*
  46.  * Define the maximum size of a dictionary.
  47.  */
  48. extern const uint dict_max_size;
  49.  
  50. /*
  51.  * Define whether dictionaries expand automatically when full.  Note that
  52.  * if dict_auto_expand is true, dict_put, dict_copy, dict_resize, and
  53.  * dict_grow cannot return e_dictfull; however, they can return e_VMerror.
  54.  * (dict_find can return e_dictfull even if dict_auto_expand is true.)
  55.  */
  56. extern bool dict_auto_expand;
  57.  
  58. /*
  59.  * Create a dictionary.
  60.  */
  61. #ifndef gs_ref_memory_DEFINED
  62. #  define gs_ref_memory_DEFINED
  63. typedef struct gs_ref_memory_s gs_ref_memory_t;
  64. #endif
  65. int dict_alloc(P3(gs_ref_memory_t *, uint maxlength, ref * pdref));
  66.  
  67. #define dict_create(maxlen, pdref)\
  68.   dict_alloc(iimemory, maxlen, pdref)
  69.  
  70. /*
  71.  * Return a pointer to a ref that holds the access attributes
  72.  * for a dictionary.
  73.  */
  74. #define dict_access_ref(pdref) (&(pdref)->value.pdict->values)
  75. /*
  76.  * Check a dictionary for read or write permission.
  77.  * Note: this does NOT check the type of its operand!
  78.  */
  79. #define check_dict_read(dref) check_read(*dict_access_ref(&dref))
  80. #define check_dict_write(dref) check_write(*dict_access_ref(&dref))
  81.  
  82. /*
  83.  * Look up a key in a dictionary.  Store a pointer to the value slot
  84.  * where found, or to the (value) slot for inserting.
  85.  * The caller is responsible for checking that the dictionary is readable.
  86.  * Return 1 if found, 0 if not and there is room for a new entry,
  87.  * Failure returns:
  88.  *      e_typecheck if the key is null;
  89.  *      e_invalidaccess if the key is a string lacking read access;
  90.  *      e_VMerror or e_limitcheck if the key is a string and the corresponding
  91.  *        error occurs from attempting to convert it to a name;
  92.  *      e_dictfull if the dictionary is full and the key is missing.
  93.  */
  94. int dict_find(P3(const ref * pdref, const ref * key, ref ** ppvalue));
  95.  
  96. /*
  97.  * Look up a (constant) C string in a dictionary.
  98.  * Return 1 if found, <= 0 if not.
  99.  */
  100. int dict_find_string(P3(const ref * pdref, const char *kstr, ref ** ppvalue));
  101.  
  102. /*
  103.  * Enter a key-value pair in a dictionary.
  104.  * The caller is responsible for checking that the dictionary is writable.
  105.  * Return 1 if this was a new entry, 0 if this replaced an existing entry.
  106.  * Failure returns are as for dict_find, except that e_dictfull doesn't
  107.  * occur if the dictionary is full but expandable, plus:
  108.  *      e_invalidaccess for an attempt to store a younger key or value into
  109.  *        an older dictionary, or as described just below;
  110.  *      e_VMerror if a VMerror occurred while trying to expand the
  111.  *        dictionary.
  112.  * Note that this procedure, and all procedures that may change the
  113.  * contents of a dictionary, take a pointer to a dictionary stack,
  114.  * so they can update the cached 'top' values and also update the cached
  115.  * value pointer in names.  A NULL pointer for the dictionary stack is
  116.  * allowed, but in this case, if the dictionary is present on any dictionary
  117.  * stack, an e_invalidaccess error will occur if cached values need updating.
  118.  * THIS ERROR CHECK IS NOT IMPLEMENTED YET.
  119.  */
  120. int dict_put(P4(ref * pdref, const ref * key, const ref * pvalue,
  121.         dict_stack_t *pds));
  122.  
  123. /*
  124.  * Enter a key-value pair where the key is a (constant) C string.
  125.  */
  126. int dict_put_string(P4(ref * pdref, const char *kstr, const ref * pvalue,
  127.                dict_stack_t *pds));
  128.  
  129. /*
  130.  * Remove a key-value pair from a dictionary.
  131.  * Return 0 or e_undefined.
  132.  */
  133. int dict_undef(P3(ref * pdref, const ref * key, dict_stack_t *pds));
  134.  
  135. /*
  136.  * Return the number of elements in a dictionary.
  137.  */
  138. uint dict_length(P1(const ref * pdref));
  139.  
  140. /*
  141.  * Return the capacity of a dictionary.
  142.  */
  143. uint dict_maxlength(P1(const ref * pdref));
  144.  
  145. /*
  146.  * Return the maximum index of a slot within a dictionary.
  147.  * Note that this may be greater than maxlength.
  148.  */
  149. uint dict_max_index(P1(const ref * pdref));
  150.  
  151. /*
  152.  * Copy one dictionary into another.
  153.  * Return 0 or e_dictfull.
  154.  * If new_only is true, only copy entries whose keys
  155.  * aren't already present in the destination.
  156.  */
  157. int dict_copy_entries(P4(const ref * dfrom, ref * dto, bool new_only,
  158.              dict_stack_t *pds));
  159.  
  160. #define dict_copy(dfrom, dto, pds) dict_copy_entries(dfrom, dto, false, pds)
  161. #define dict_copy_new(dfrom, dto, pds) dict_copy_entries(dfrom, dto, true, pds)
  162.  
  163. /*
  164.  * Grow or shrink a dictionary.
  165.  * Return 0, e_dictfull, or e_VMerror.
  166.  */
  167. int dict_resize(P3(ref * pdref, uint newmaxlength, dict_stack_t *pds));
  168.  
  169. /*
  170.  * Grow a dictionary in the same way as dict_put does.
  171.  * We export this for some special-case code in zop_def.
  172.  */
  173. int dict_grow(P2(ref * pdref, dict_stack_t *pds));
  174.  
  175. /*
  176.  * Ensure that a dictionary uses the unpacked representation for keys.
  177.  * (This is of no interest to ordinary clients.)
  178.  */
  179. int dict_unpack(P2(ref * pdref, dict_stack_t *pds));
  180.  
  181. /*
  182.  * Prepare to enumerate a dictionary.
  183.  * Return an integer suitable for the first call to dict_next.
  184.  */
  185. int dict_first(P1(const ref * pdref));
  186.  
  187. /*
  188.  * Enumerate the next element of a dictionary.
  189.  * index is initially the result of a call on dict_first.
  190.  * Either store a key and value at eltp[0] and eltp[1]
  191.  * and return an updated index, or return -1
  192.  * to signal that there are no more elements in the dictionary.
  193.  */
  194. int dict_next(P3(const ref * pdref, int index, ref * eltp));
  195.  
  196. /*
  197.  * Given a value pointer return by dict_find, return an index that
  198.  * identifies the entry within the dictionary. (This may, but need not,
  199.  * be the same as the index returned by dict_next.)
  200.  * The index is in the range [0..max_index-1].
  201.  */
  202. int dict_value_index(P2(const ref * pdref, const ref * pvalue));
  203.  
  204. /*
  205.  * Given an index in [0..max_index-1], as returned by dict_value_index,
  206.  * return the key and value, as returned by dict_next.
  207.  * If the index designates an unoccupied entry, return e_undefined.
  208.  */
  209. int dict_index_entry(P3(const ref * pdref, int index, ref * eltp));
  210.  
  211. /*
  212.  * The following are some internal details that are used in both the
  213.  * implementation and some high-performance clients.
  214.  */
  215.  
  216. /* On machines with reasonable amounts of memory, we round up dictionary
  217.  * sizes to the next power of 2 whenever possible, to allow us to use
  218.  * masking rather than division for computing the hash index.
  219.  * Unfortunately, if we required this, it would cut the maximum size of a
  220.  * dictionary in half.  Therefore, on such machines, we distinguish
  221.  * "huge" dictionaries (dictionaries whose size is larger than the largest
  222.  * power of 2 less than dict_max_size) as a special case:
  223.  *
  224.  *      - If the top dictionary on the stack is huge, we set the dtop
  225.  *      parameters so that the fast inline lookup will always fail.
  226.  *
  227.  *      - For general lookup, we use the slower hash_mod algorithm for
  228.  *      huge dictionaries.
  229.  */
  230. #define dict_max_non_huge ((uint)(max_array_size / 2 + 1))
  231.  
  232. /* Define the hashing function for names. */
  233. /* We don't have to scramble the index, because */
  234. /* indices are assigned in a scattered order (see name_ref in iname.c). */
  235. #define dict_name_index_hash(nidx) (nidx)
  236.  
  237. /* Hash an arbitrary non-negative or unsigned integer into a dictionary. */
  238. #define dict_hash_mod_rem(hash, size) ((hash) % (size))
  239. #define dict_hash_mod_mask(hash, size) ((hash) & ((size) - 1))
  240. #define dict_hash_mod_small(hash, size) dict_hash_mod_rem(hash, size)
  241. #define dict_hash_mod_inline_small(hash, size) dict_hash_mod_rem(hash, size)
  242. #define dict_hash_mod_large(hash, size)\
  243.   (size > dict_max_non_huge ? dict_hash_mod_rem(hash, size) :\
  244.    dict_hash_mod_mask(hash, size))
  245. #define dict_hash_mod_inline_large(hash, size) dict_hash_mod_mask(hash, size)
  246. /* Round up the requested size of a dictionary.  Return 0 if too big. */
  247. uint dict_round_size_small(P1(uint rsize));
  248. uint dict_round_size_large(P1(uint rsize));
  249.  
  250. /* Choose the algorithms depending on the size of memory. */
  251. #if arch_small_memory
  252. #  define dict_hash_mod(h, s) dict_hash_mod_small(h, s)
  253. #  define dict_hash_mod_inline(h, s) dict_hash_mod_inline_small(h, s)
  254. #  define dict_round_size(s) dict_round_size_small(s)
  255. #else
  256. #  ifdef DEBUG
  257. #    define dict_hash_mod(h, s)\
  258.        (gs_debug_c('.') ? dict_hash_mod_small(h, s) :\
  259.     dict_hash_mod_large(h, s))
  260. #    define dict_hash_mod_inline(h, s)\
  261.        (gs_debug_c('.') ? dict_hash_mod_inline_small(h, s) :\
  262.     dict_hash_mod_inline_large(h, s))
  263. #    define dict_round_size(s)\
  264.        (gs_debug_c('.') ? dict_round_size_small(s) :\
  265.     dict_round_size_large(s))
  266. #  else
  267. #    define dict_hash_mod(h, s) dict_hash_mod_large(h, s)
  268. #    define dict_hash_mod_inline(h, s) dict_hash_mod_inline_large(h, s)
  269. #    define dict_round_size(s) dict_round_size_large(s)
  270. #  endif
  271. #endif
  272.  
  273. #endif /* idict_INCLUDED */
  274.